1. Field of the Invention
The present invention relates to a method and associated apparatus for selecting motion vectors for use in a video motion estimator. Such video motion estimators are typically used in video processing applications, particularly for the purpose of video compression.
2. Description of the Related Art
MPEG (Moving Picture Expert Group) standards are used in many current and emerging video products. They are implemented in digital television set-top boxes, video-telephone, High Definition Television (HDTV) decoders, video conferencing and other applications. These applications benefit from video compression in that they require less storage capacity for archived video information, less bandwidth for the transmission of the video information, or a combination of both.
Various video compression techniques are used to reduce the substantial amount of data involved in encoding video images. One such example is a transform coding using a Discrete Cosine Transform (DCT) process that reduces spatial correlation. Another example is motion compensation coding that reduces temporal correlation between two successive frames.
The motion compensation is used to predict the current frame data from previous frame data based on an estimation of motion between the current and the previous video frame. The premise of this motion estimation is that in most cases, consecutive video frames will be similar except for changes induced by objects moving within the frames. In the trivial case of zero motion between frames, it is easily and efficiently predicted that the current frame is a duplicate of the prediction frame. In such a case, the only information needed to be transmitted to the decoder is the syntactic overhead (i.e., the coding scheme used to indicate the identity between successive frames) necessary to reconstruct the picture from the original reference frame.
When there is motion in the images, the displacement of part of the current frame with respect to previous or future frame is estimated. Therefore, one or more motion vectors, representing the displacement of certain pixels between the previous and the current frames, are determined to represent the motion.
Motion vectors from a sequence of video frames are usually determined by a block matching algorithm. The algorithm is arranged to search for the best match block of the current frame from the candidate blocks inside a search window in the reference frame. The block matching algorithm divides the image into square blocks which contain ‘N×N’ pixels, and then compares each block in the current frame (current block) with those within a reduced area of the reference frame (search window) looking for the closest match.
Absolute error (AE) is the sum of differences in the luminance level of all pixels between the current block and reference block. And the smallest AE among the calculated AEs is used to determine the motion vector as a measure of the displacement of the pixels between the reference block and the candidate block in the search window. Alternatively, Square Error (SE), the square of the sum of differences in the luminance level of all pixels between the current block and the reference block, may be used for motion vector determination.
Within a search window, there may be a plurality of equivalent AEs found during block matching. This particular problem is addressed in U.S. Pat. No. 5,327,232. According to this patent, the AEs are compared and a subset, consisting of all minimum AEs equal to the smallest value, is defined. A further subset of candidate vectors from the subset of said minimum AEs is then derived. Each candidate vector, representing the displacement of the pixels between the current block and the search window, represents the corresponding AE equal to the smallest value. A predetermined motion vector, retrieved from a storage means, is compared with the subset of said candidate vectors to determine the candidate vector closest to the predetermined motion vector. The closest candidate vector is defined as the motion vector of the current block and is then stored in the storage means as the predetermined motion vector for subsequent current blocks.
A norm function with reference to a user defined preferred point can be used to select one of the motion vectors, the preferred point having been previously described in the search window. According to U.S. Pat. No. 5,717,615, the norm function of the said vectors is created according to the function: max {|X|, |Y|} or √{square root over ((X2+Y2))}, where X and Y represent the co-ordinates of a vector. The norm of the search points are computed and compared when the corresponding AE values are equal to the said smallest AE.
Calculation of the norm function for each position in the search window demands a large amount of computational capacity. The cost of implementing √{square root over ((X2+Y2))} for each position is high as a large processing capacity must be provided. The accuracy of max {|X|, |Y|} affects the quality of detected motion vectors, and hence the decoded image. It is therefore difficult to use approximations to reduce the computational overhead without adversely affecting image quality.
Typically, multiple systolic arrays (e.g., 4×16×8, or 8×8×8, etc) are used for searching a larger search window. The number of norm functions to be calculated is proportional to the number of arrays. Furthermore, the number of comparators required to compare AEs in parallel with the norms is significantly increased. For each search position, two comparators are needed for the AE and the norm value. Therefore, for a multiple systolic array of 4×16×8, two comparators are needed for sequential comparison. If the number of multiple systolic arrays is increased to four, 4×2 comparators are required for determination of the motion vector.